#lang racket

;; By default, Racket doesn't have set-car! and set-cdr! functions.  The
;; following line allows us to use those:
(require r5rs)
;; Unfortunately, it does this by making cons return a "mutable pair"
;; instead of a "pair", which means that many built-ins may fail
;; mysteriously because they expect a pair, but get a mutable pair.
;; Re-define a few common functions in terms of car and friends, which
;; the above line make work with mutable pairs.
(define first car)
(define rest cdr)
(define second cadr)
(define third caddr)
;; We also tell DrRacket to print mutable pairs using the compact syntax
;; for ordinary pairs.
(print-as-expression #f)
(print-mpair-curly-braces #f)

"Problem 2: Simpler simplifier"
;;

; Write your simplifier abstraction here.
"... abstraction"
(define (make-simplifier match replace)
  ;make simplier returns a function that takes in an expresion and returns a modified expression
  (lambda (exp)
    (if (match exp)
        (replace exp)
        exp)))
  
;tests
((make-simplifier (lambda (exp) (< exp 0)) (lambda (exp) 0)) 6) ;6
((make-simplifier (lambda (exp) (< exp 0)) (lambda (exp) 0)) -19) ;0

"... simplify"
(define (simplify exp simplifier)
  (if (not (list? exp))
      (simplifier exp)
      (let ((a (second exp))(b (third exp)))
        (set-car! (rest exp) (simplify a simplifier))
        (set-car! (rest (rest exp)) (simplify b simplifier))
        (simplifier exp)
        )))
;tests
(simplify '(+ 42 (* x x)) (make-simplifier (lambda (exp) (eq? exp 'x))(lambda (exp) 17)))

;;
"Problem 1: Identity problems"
;;
(define (remove-additive-identity exp)
  (simplify exp
            (make-simplifier
             (lambda (exp)
               (and (list? exp)
                    (eq? (first exp) '+)
                    (eq? (third exp) '0)))
             (lambda (exp)
               (set! exp (second exp))
               exp)))
;  (define (helper exp)
;    (define a (second exp))
;    (define b (third exp))
;    (if (equal? (first exp) `+)
;      (begin
;        (set! a (remove-additive-identity a))
;        (set! b (remove-additive-identity b))
;        (set-car! (rest exp) a)
;        (set-car! (rest (rest exp)) b)
;        ;(if (equal? a '0) (set! exp b)) ;; not possible
;        (if (equal? b '0) (set! exp a))
;        )
;      )
;    exp
;  )
;  
;  (if (list? exp)  ; if not list, return original expression      
;    (helper exp)
;    exp)
)

(remove-additive-identity '(+ 17 0))
(remove-additive-identity '(+ x 0))
(remove-additive-identity '(+ 17 42))
(remove-additive-identity '(* 17 0))
(remove-additive-identity 17)
(remove-additive-identity '(+ 42 (+ 17 0)))
(remove-additive-identity '(+ (+ 17 0) 0))
(remove-additive-identity '(+ (+ 4 0) (+ 0 0)))

"... part 2"
(define (remove-multiplicative-identity exp)
  (simplify exp
            (make-simplifier
             (lambda (exp)
               (and (list? exp)
                    (eq? (first exp) '*)
                    (eq? (third exp) '1)))
             (lambda (exp)
               (set! exp (second exp))
               exp)))
;  (define (helper exp)
;    (define a (second exp))
;    (define b (third exp))
;    (if (equal? (car exp) `*)
;      (begin
;        (set! a (remove-multiplicative-identity a))
;        (set! b (remove-multiplicative-identity b))
;        (set-car! (rest exp) a)
;        (set-car! (rest (rest exp)) b)
;        ;(if (equal? a '0) (set! exp b)) ;; not possible
;        (if (equal? b '1) (set! exp a))
;        )
;      )
;    exp
;  )
;  
;  (if (list? exp)        
;    (helper exp)
;    exp)
)

(remove-multiplicative-identity '(* 17 1))
(remove-multiplicative-identity '(* x 1))
(remove-multiplicative-identity '(* 17 42))
(remove-multiplicative-identity '(+ 17 1))
(remove-multiplicative-identity 17)
(remove-multiplicative-identity '(* 42 (* 17 1)))
(remove-multiplicative-identity '(* (* 17 1) 1))


;;

;; ---- Pattern matching ----

;;
;; Problem 3: These laws are binding
;;

; Write your binding and mapping abstractions here.
(define (make-mapping);empty mapping
  (define mapping '())
  mapping
  )

(define (make-binding name sub_exp) ; making a binding with a pair of information
  (define binding (cons name sub_exp))
  binding
  )

(define (binding-name binding)
  (car binding));the name is the first element in the binding
(define (binding-value binding)
  (cdr binding))


(define (mapping-add-binding! mapping binding) ;binding is a pair (name, sub-expression)
  ;add binding to the end of the mapping list
  ;mapping is a list of pairs
  ;can easily add binding to the front of mapping
  (set! mapping (cons binding mapping))
  mapping
  )

(define (mapping-lookup mapping name) ;search for name in mapping's set of bindings, return binding or false
  (if (null? mapping)
      #f
      (let ((binding (first mapping)))
        (if (equal? name (car binding))
            binding
            (mapping-lookup (cdr mapping) name))))
  )

(define (mapping-add one two)
  (define (helper one two)
    (if (null? two)
        one
        (begin
          (set! one (mapping-add-binding! one (first two)))
          (set! two (rest two))
          (helper one two))))
  (helper one two)
  )

;tests
"Problem 3"
(define amap (make-mapping))
(define bind (make-binding "ALPHA" 'x))
(define one (make-binding "BETA" 'x))
amap
bind
(set! amap (mapping-add-binding! amap bind))
amap
(set! amap (mapping-add-binding! amap one))
amap
(mapping-lookup amap "BETA")
(mapping-lookup amap "ALPHA")
amap

;;
;; Problem 4: Matchmaker, matchmaker, make me a match...
;;
(define (match-position? exp)
  (if (list? exp)
      (if (eq? '? (first exp))
          (if (not (null? (second exp)))
              #t
              #f)
          #f)
      #f))
(define (match-position-name exp);returns the name given that exp is a match-position
  (second exp)) ;The name is just the second element of the exp

(define (match-pattern pattern expression)
  (let ((mapping (make-mapping)))
    (if (match-position? pattern) 
        ;if match position, make binding
        (cond ((or (number? expression)(symbol? expression))
               ;bind expression with name after '?, add to mapping, then return mapping
               (begin
                 (set! mapping (mapping-add-binding! mapping (make-binding (second pattern) expression)))
                 mapping)) 
              ((list? expression) #f)
              (else #f))
        ;if not match position, check operator
        (if (and (list? expression) (list? pattern))
            (if (eq? (first expression) (first pattern))
                ;if match, check for each part of expression
                (let ((A (match-pattern (second pattern) (second expression)))
                      (B (match-pattern (third pattern) (third expression))))
                  (if (or (boolean? A) (boolean? B))
                      #f
                      (begin
                        (set! mapping (mapping-add A B))
                        mapping))) ; need to add A to B
                #f)
            (if (eq? expression pattern)
                mapping
                #f)))
;    Old Code:
;    (define (helper exp)
;      (if (list? exp)
;        (begin
;          (if (match-position? exp)
;             ;get name, create binding, add binding to mapping
;            (begin
;              (set! returnMap (mapping-add-binding! returnMap (make-binding (match-position-name expression))))
;              returnMap)
;            #f))
;         #f)
;      )
;     expression
    ))
"Problem 4"
(display 1)
(match-pattern '(? ANYTHING) '(+ 1 0))
(display 2)
(match-pattern '(? ANYTHING) 0)
(display 3)
(match-pattern '(+ (? ANYTHING) 0) '(+ 1 0))
(match-pattern '(* (+ (? Otherthing) 0) (? Something)) '(*(+ 1 0) 5))


;;
;; Problem 5: Don't make me repeat myself (optional)
;;
"Problem 5 Optional"
(match-pattern '(+ (? ANYTHING) (? ANYTHING)) '(+ 1 1))
(match-pattern '(+ (? ANYTHING) (? ANYTHING)) '(+ 1 2))

;(define (mapping-add-binding! mapping binding)
;  ;add binding to the end of the mapping list
;  ;mapping is a list of pairs
;  ;can easily add binding to the front of mapping
;  
;  (set! mapping (cons binding mapping))
;  mapping)

;(define (match-pattern pattern expression)
;  'updated-code-here)


;;
;; Problem 6: Putting it all together
;; Returns a simplifier
(define (make-pattern-simplifier pattern transformer)
  (lambda (exp)
    (let ((matches (match-pattern pattern exp)))
      (if (boolean? matches)
          exp
          (transformer matches)))))

"Problem 6"
(simplify 
 '(+ 17 0) 
 (make-pattern-simplifier 
  '(+ (? ALPHA) 0) 
  (lambda(matches) 
    (binding-value(mapping-lookup matches 'ALPHA)))))


;;
;; Problem 7: Pick a number, any number (optional)
;;


;;
;; Problem 8: Now you're just fixing for points (optional)
;;



